<!DOCTYPE html>
<html >
<head>

    <!--[if lt IE 9]>
        <style>body {display: none; background: none !important} </style>
        <meta http-equiv="Refresh" Content="0; url=//outdatedbrowser.com/" />
    <![endif]-->

<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
<meta name="format-detection" content="telephone=no" />
<meta name="author" content="xiaoyou" />



<meta name="description" content="在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？">
<meta name="keywords" content="唯一ID">
<meta property="og:type" content="article">
<meta property="og:title" content="Leaf——美团点评分布式ID生成系统">
<meta property="og:url" content="http://yoursite.com/2017/04/22/meituan-id/index.html">
<meta property="og:site_name" content="Lost Youth">
<meta property="og:description" content="在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/image1.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/image3.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/image4.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/image6.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/snowflake-workerid.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/fallback.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/snowflake.flow.png">
<meta property="og:image" content="http://oo77gy3uq.bkt.clouddn.com/qrcode_for_gh.jpg">
<meta property="og:updated_time" content="2017-04-26T06:06:38.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Leaf——美团点评分布式ID生成系统">
<meta name="twitter:description" content="在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？">
<meta name="twitter:image" content="http://oo77gy3uq.bkt.clouddn.com/image1.png">

<link rel="apple-touch-icon" href= "/apple-touch-icon.png">


    <link rel="alternate" href="/atom.xml" title="Lost Youth" type="application/atom+xml">



    <link rel="shortcut icon" href="/favicon.png">



    <link href="//cdn.bootcss.com/animate.css/3.5.1/animate.min.css" rel="stylesheet">



    <link href="//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.css" rel="stylesheet">



    <script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
    <link href="//cdn.bootcss.com/pace/1.0.2/themes/blue/pace-theme-minimal.css" rel="stylesheet">


<link rel="stylesheet" href="/css/style.css">



<link href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet">


<title>Leaf——美团点评分布式ID生成系统 | Lost Youth</title>

<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
<script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>

<script>
    var yiliaConfig = {
        fancybox: true,
        animate: true,
        isHome: false,
        isPost: true,
        isArchive: false,
        isTag: false,
        isCategory: false,
        fancybox_js: "//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.js",
        scrollreveal: "//cdn.bootcss.com/scrollReveal.js/3.1.4/scrollreveal.min.js",
        search: undefined
    }
</script>


    <script> yiliaConfig.jquery_ui = [false]; </script>



    <script> yiliaConfig.rootUrl = "\/";</script>






</head>
<body>
  <div id="container">
    <div class="left-col">
    <div class="overlay"></div>
<div class="intrude-less">
    <header id="header" class="inner">
        <a href="/" class="profilepic">
            <img src="/img/avatar.png" class="animated zoomIn">
        </a>
        <hgroup>
          <h1 class="header-author"><a href="/">xiaoyou</a></h1>
        </hgroup>

        

        


        
            <div id="switch-btn" class="switch-btn">
                <div class="icon">
                    <div class="icon-ctn">
                        <div class="icon-wrap icon-house" data-idx="0">
                            <div class="birdhouse"></div>
                            <div class="birdhouse_holes"></div>
                        </div>
                        <div class="icon-wrap icon-ribbon hide" data-idx="1">
                            <div class="ribbon"></div>
                        </div>
                        
                        <div class="icon-wrap icon-link hide" data-idx="2">
                            <div class="loopback_l"></div>
                            <div class="loopback_r"></div>
                        </div>
                        
                        
                        <div class="icon-wrap icon-me hide" data-idx="3">
                            <div class="user"></div>
                            <div class="shoulder"></div>
                        </div>
                        
                    </div>
                    
                </div>
                <div class="tips-box hide">
                    <div class="tips-arrow"></div>
                    <ul class="tips-inner">
                        <li>菜单</li>
                        <li>标签</li>
                        
                        <li>友情链接</li>
                        
                        
                        <li>关于我</li>
                        
                    </ul>
                </div>
            </div>
        

        <div id="switch-area" class="switch-area">
            <div class="switch-wrap">
                <section class="switch-part switch-part1">
                    <nav class="header-menu">
                        <ul>
                        
                            <li><a href="/">Home</a></li>
                        
                            <li><a href="/archives">Archives</a></li>
                        
                            <li><a href="/tools">Tools</a></li>
                        
                            <li><a href="/about">About</a></li>
                        
                        </ul>
                    </nav>
                    <nav class="header-nav">
                        <ul class="social">
                            
                                <a class="fa Email" href="mailto:123@123.com" title="Email"></a>
                            
                                <a class="fa GitHub" href="#" title="GitHub"></a>
                            
                                <a class="fa RSS" href="/atom.xml" title="RSS"></a>
                            
                        </ul>
                    </nav>
                </section>
                
                
                <section class="switch-part switch-part2">
                    <div class="widget tagcloud" id="js-tagcloud">
                        <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Git/">Git</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Java8/">Java8</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/MySql/">MySql</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RocketMQ/">RocketMQ</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Spring-Boot/">Spring Boot</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Tomcat/">Tomcat</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/分布式-服务化/">分布式 服务化</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/唯一ID/">唯一ID</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/微服务/">微服务</a></li></ul>
                    </div>
                </section>
                
                
                
                <section class="switch-part switch-part3">
                    <div id="js-friends">
                    
                      <a class="main-nav-link switch-friends-link" href="https://hexo.io">Hexo</a>
                    
                      <a class="main-nav-link switch-friends-link" href="https://pages.github.com/">GitHub</a>
                    
                      <a class="main-nav-link switch-friends-link" href="http://moxfive.xyz/">MOxFIVE</a>
                    
                    </div>
                </section>
                

                
                
                <section class="switch-part switch-part4">
                
                    <div id="js-aboutme">Man</div>
                </section>
                
            </div>
        </div>
    </header>                
</div>
    </div>
    <div class="mid-col">
      <nav id="mobile-nav">
      <div class="overlay">
          <div class="slider-trigger"></div>
          <h1 class="header-author js-mobile-header hide"><a href="/" title="回到主页">xiaoyou</a></h1>
      </div>
    <div class="intrude-less">
        <header id="header" class="inner">
            <a href="/" class="profilepic">
                <img src="/img/avatar.png" class="animated zoomIn">
            </a>
            <hgroup>
              <h1 class="header-author"><a href="/" title="回到主页">xiaoyou</a></h1>
            </hgroup>
            
            <nav class="header-menu">
                <ul>
                
                    <li><a href="/">Home</a></li>
                
                    <li><a href="/archives">Archives</a></li>
                
                    <li><a href="/tools">Tools</a></li>
                
                    <li><a href="/about">About</a></li>
                
                <div class="clearfix"></div>
                </ul>
            </nav>
            <nav class="header-nav">
                        <ul class="social">
                            
                                <a class="fa Email" target="_blank" href="mailto:123@123.com" title="Email"></a>
                            
                                <a class="fa GitHub" target="_blank" href="#" title="GitHub"></a>
                            
                                <a class="fa RSS" target="_blank" href="/atom.xml" title="RSS"></a>
                            
                        </ul>
            </nav>
        </header>                
    </div>
    <link class="menu-list" tags="标签" friends="友情链接" about="关于我"/>
</nav>
      <div class="body-wrap"><article id="post-meituan-id" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/2017/04/22/meituan-id/" class="article-date">
      <time datetime="2017-04-22T13:03:00.000Z" itemprop="datePublished">2017-04-22</time>
</a>


    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      Leaf——美团点评分布式ID生成系统
    </h1>
  

      </header>
      
      <div class="article-info article-info-post">
        

        
    <div class="article-tag tagcloud">
        <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/唯一ID/">唯一ID</a></li></ul>
    </div>

        <div class="clearfix"></div>
      </div>
      
    
    <div class="article-entry" itemprop="articleBody">
      
          
        <p> 原文地址: <a href="http://tech.meituan.com/MT_Leaf.html" target="_blank" rel="external">http://tech.meituan.com/MT_Leaf.html</a></p>
<h1 id="背景"><a href="#背景" class="headerlink" title="背景"></a>背景</h1><p>在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。概括下来，那业务系统对ID号的要求有哪些呢？</p>
<ol>
<li>全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。</li>
<li>趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。</li>
<li>单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。</li>
<li>信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。</li>
</ol>
<p>上述123对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。</p>
<p>同时除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高，想象一下，如果ID生成系统瘫痪，整个美团点评支付、优惠券发券、骑手派单等关键动作都无法执行，这就会带来一场灾难。</p>
<p>由此总结下一个ID生成系统应该做到如下几点：</p>
<ol>
<li>平均延迟和TP999延迟都要尽可能低；</li>
<li>可用性5个9；</li>
<li>高QPS。</li>
</ol>
<h1 id="常见方法介绍"><a href="#常见方法介绍" class="headerlink" title="常见方法介绍"></a>常见方法介绍</h1><h3 id="UUID"><a href="#UUID" class="headerlink" title="UUID"></a>UUID</h3><p>UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：<code>550e8400-e29b-41d4-a716-446655440000</code>，到目前为止业界一共有5种方式生成UUID，详情见IETF发布的UUID规范 <a href="http://www.ietf.org/rfc/rfc4122.txt" target="_blank" rel="external">A Universally Unique IDentifier (UUID) URN Namespace</a>。</p>
<p>优点：</p>
<ul>
<li>性能非常高：本地生成，没有网络消耗。</li>
</ul>
<p>缺点：</p>
<ul>
<li>不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用。</li>
<li><p>信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。</p>
</li>
<li><p>ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用：</p>
<p>  ① MySQL官方有明确的建议主键要尽量越短越好[4]，36个字符长度的UUID不符合要求。</p>
<blockquote>
<p>All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.<strong> <em>If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key</em></strong>.</p>
</blockquote>
<p>  ② 对MySQL索引不利：如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。</p>
</li>
</ul>
<h3 id="类snowflake方案"><a href="#类snowflake方案" class="headerlink" title="类snowflake方案"></a>类snowflake方案</h3><p>这种方案大致来说是一种以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法，这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在snowflake中的64-bit分别表示如下图（图片来自网络）所示：</p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/image1.png" alt="image"></p>
<p>41-bit的时间可以表示（1L There are no two identical leaves in the world</p>
<blockquote>
<p>“世界上没有两片相同的树叶”</p>
</blockquote>
<p>综合对比上述几种方案，每种方案都不完全符合我们的要求。所以Leaf分别在上述第二种和第三种方案上做了相应的优化，实现了Leaf-segment和Leaf-snowflake方案。</p>
<h3 id="Leaf-segment数据库方案"><a href="#Leaf-segment数据库方案" class="headerlink" title="Leaf-segment数据库方案"></a>Leaf-segment数据库方案</h3><p>第一种Leaf-segment方案，在使用数据库的方案上，做了如下改变：</p>
<ul>
<li>原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。</li>
<li>各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。</li>
</ul>
<p>数据库表设计如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line">+-------------+--------------+------+-----+-------------------+-----------------------------+</div><div class="line">| Field       | Type         | Null | Key | Default           | Extra                       |</div><div class="line">+-------------+--------------+------+-----+-------------------+-----------------------------+</div><div class="line">| biz_tag     | varchar(128) | NO   | PRI |                   |                             |</div><div class="line">| max_id      | bigint(20)   | NO   |     | 1                 |                             |</div><div class="line">| step        | int(11)      | NO   |     | NULL              |                             |</div><div class="line">| desc        | varchar(256) | YES  |     | NULL              |                             |</div><div class="line">| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |</div><div class="line">+-------------+--------------+------+-----+-------------------+-----------------------------+</div></pre></td></tr></table></figure>
<p>重要字段说明：biz_tag用来区分业务，max_id表示该biz_tag目前所被分配的ID号段的最大值，step表示每次分配的号段长度。原来获取ID每次都需要写数据库，现在只需要把step设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step，大致架构如下图所示：</p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/image3.png" alt="image"></p>
<p>test_tag在第一台Leaf机器上是1~1000的号段，当这个号段用完时，会去加载另一个长度为step=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的biz_tag这条数据的max_id会从3000被更新成4000，更新号段的SQL语句如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line">Begin</div><div class="line">UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx</div><div class="line">SELECT tag, max_id, step FROM table WHERE biz_tag=xxx</div><div class="line">Commit</div></pre></td></tr></table></figure>
<p>这种模式有以下优缺点：</p>
<p>优点：</p>
<ul>
<li>Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。</li>
<li>ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。</li>
<li>容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。</li>
<li>可以自定义max_id的大小，非常方便业务从原有的ID方式上迁移过来。</li>
</ul>
<p>缺点：</p>
<ul>
<li>ID号码不够随机，能够泄露发号数量的信息，不太安全。</li>
<li>TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。</li>
<li>DB宕机会造成整个系统不可用。</li>
</ul>
<h3 id="双buffer优化"><a href="#双buffer优化" class="headerlink" title="双buffer优化"></a>双buffer优化</h3><p>对于第二个缺点，Leaf-segment做了一些优化，简单的说就是：</p>
<p>Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。</p>
<p>为此，我们希望DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。详细实现如下图所示：</p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/image4.png" alt="image"></p>
<p>采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。</p>
<ul>
<li><p>每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。</p>
</li>
<li><p>每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。</p>
</li>
</ul>
<h3 id="Leaf高可用容灾"><a href="#Leaf高可用容灾" class="headerlink" title="Leaf高可用容灾"></a>Leaf高可用容灾</h3><p>对于第三点“DB可用性”问题，我们目前采用一主两从的方式，同时分机房部署，Master和Slave之间采用<strong>半同步方式[5]</strong>同步数据。同时使用公司Atlas数据库中间件(已开源，改名为<a href="http://tech.meituan.com/dbproxy-introduction.html" target="_blank" rel="external">DBProxy</a>)做主从切换。当然这种方案在一些情况会退化成异步模式，甚至在<strong>非常极端</strong>情况下仍然会造成数据不一致的情况，但是出现的概率非常小。如果你的系统要保证100%的数据强一致，可以选择使用“类Paxos算法”实现的强一致MySQL方案，如MySQL 5.7前段时间刚刚GA的<a href="https://dev.mysql.com/doc/refman/5.7/en/group-replication.html" target="_blank" rel="external">MySQL Group Replication</a>。但是运维成本和精力都会相应的增加，根据实际情况选型即可。</p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/image6.png" alt="image"></p>
<p>同时Leaf服务分IDC部署，内部的服务化框架是“MTthrift RPC”。服务调用的时候，根据负载均衡算法会优先调用同机房的Leaf服务。在该IDC内Leaf服务不可用的时候才会选择其他机房的Leaf服务。同时服务治理平台OCTO还提供了针对服务的过载保护、一键截流、动态流量分配等对服务的保护措施。</p>
<h1 id="Leaf-snowflake方案"><a href="#Leaf-snowflake方案" class="headerlink" title="Leaf-snowflake方案"></a>Leaf-snowflake方案</h1><p>Leaf-segment方案可以生成趋势递增的ID，同时ID号是可计算的，不适用于订单ID生成场景，比如竞对在两天中午12点分别下单，通过订单id号相减就能大致计算出公司一天的订单量，这个是不能忍受的。面对这一问题，我们提供了 Leaf-snowflake方案。</p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/snowflake-workerid.png" alt="image"></p>
<p>Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号。对于workerID的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf服务规模较大，动手配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。Leaf-snowflake是按照下面几个步骤启动的：</p>
<ol>
<li>启动Leaf-snowflake服务，连接Zookeeper，在leaf_forever父节点下检查自己是否已经注册过（是否有该顺序子节点）。</li>
<li>如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。</li>
<li>如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。</li>
</ol>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/fallback.png" alt="image"></p>
<h3 id="弱依赖ZooKeeper"><a href="#弱依赖ZooKeeper" class="headerlink" title="弱依赖ZooKeeper"></a>弱依赖ZooKeeper</h3><p>除了每次会去ZK拿数据以外，也会在本机文件系统上缓存一个workerID文件。当ZooKeeper出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。这样做到了对三方组件的弱依赖。一定程度上提高了SLA</p>
<h3 id="解决时钟问题"><a href="#解决时钟问题" class="headerlink" title="解决时钟问题"></a>解决时钟问题</h3><p>因为这种方案依赖时间，如果机器的时钟发生了回拨，那么就会有可能生成重复的ID号，需要解决时钟回退的问题。</p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/snowflake.flow.png" alt="image"></p>
<p>参见上图整个启动流程图，服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点：</p>
<ol>
<li>若写过，则用自身系统时间与leaf_forever/${self}节点记录时间做比较，若小于leaf_forever/${self}时间则认为机器时间发生了大步长回拨，服务启动失败并报警。</li>
<li>若未写过，证明是新服务节点，直接创建持久节点leaf_forever/${self}并写入自身系统时间，接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize。</li>
<li>若abs( 系统时间-sum(time)/nodeSize ) </li>
</ol>
<p>由于强依赖时钟，对时间的要求比较敏感，在机器工作时NTP同步也会造成秒级别的回退，建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE，等时钟追上即可。<strong>或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警</strong>，如下：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div></pre></td><td class="code"><pre><div class="line">//发生了回拨，此刻时间小于上次发号时间</div><div class="line">if (timestamp &lt; lastTimestamp) &#123;</div><div class="line"></div><div class="line">           long offset = lastTimestamp - timestamp;</div><div class="line">           if (offset &lt;= 5) &#123;</div><div class="line">               try &#123;</div><div class="line">                   //时间偏差大小小于5ms，则等待两倍时间</div><div class="line">                   wait(offset &lt;&lt; 1);//wait</div><div class="line">                   timestamp = timeGen();</div><div class="line">                   if (timestamp &lt; lastTimestamp) &#123;</div><div class="line">                      //还是小于，抛异常并上报</div><div class="line">                       throwClockBackwardsEx(timestamp);</div><div class="line">                     &#125;    </div><div class="line">               &#125; catch (InterruptedException e) &#123;  </div><div class="line">                  throw  e;</div><div class="line">               &#125;</div><div class="line">           &#125; else &#123;</div><div class="line">               //throw</div><div class="line">               throwClockBackwardsEx(timestamp);</div><div class="line">           &#125;</div><div class="line">       &#125;</div><div class="line">//分配ID</div></pre></td></tr></table></figure>
<p><strong>从上线情况来看，在2017年闰秒出现那一次出现过部分机器回拨，由于Leaf-snowflake的策略保证，成功避免了对业务造成的影响。</strong></p>
<h1 id="Leaf现状"><a href="#Leaf现状" class="headerlink" title="Leaf现状"></a>Leaf现状</h1><p>Leaf在美团点评公司内部服务包含金融、支付交易、餐饮、外卖、酒店旅游、猫眼电影等众多业务线。目前Leaf的性能在4C8G的机器上QPS能压测到近5w/s，TP999 1ms，已经能够满足大部分的业务的需求。每天提供亿数量级的调用量，作为公司内部公共的基础技术设施，必须保证高SLA和高性能的服务，我们目前还仅仅达到了及格线，还有很多提高的空间。</p>
<h1 id="作者简介"><a href="#作者简介" class="headerlink" title="作者简介"></a>作者简介</h1><p>照东，美团点评基础架构团队成员，主要参与<a href="http://tech.meituan.com/mt-mtrace.html" target="_blank" rel="external">美团大型分布式链路跟踪系统Mtrace</a>和美团点评分布式ID生成系统Leaf的开发工作。曾就职于阿里巴巴，2016年7月加入美团。</p>
<p>最后做一个招聘广告：如果你对大规模分布式环境下的服务治理、分布式会话链追踪等系统感兴趣，诚挚欢迎投递简历至：zhangjinlu#meituan.com。</p>
<h1 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h1><ol>
<li>施瓦茨. 高性能MySQL[M]. 电子工业出版社, 2010:162-171.</li>
<li><a href="https://zh.wikipedia.org/wiki/%E9%80%9A%E7%94%A8%E5%94%AF%E4%B8%80%E8%AF%86%E5%88%AB%E7%A0%81" target="_blank" rel="external">维基百科：UUID</a>.</li>
<li><a href="https://github.com/twitter/snowflake" target="_blank" rel="external">snowflake</a>.</li>
<li><a href="https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html" target="_blank" rel="external">MySQL: Clustered and Secondary Indexes</a>.</li>
<li><a href="https://dev.mysql.com/doc/refman/5.5/en/replication-semisync.html" target="_blank" rel="external">半同步复制 Semisynchronous Replication</a>.</li>
</ol>
<p><strong>不想错过技术博客更新？想给文章评论、和作者互动？第一时间获取技术沙龙信息？</strong></p>
<p><strong>请关注我们的官方微信公众号“美团点评技术团队”。现在就拿出手机，扫一扫：</strong></p>
<p><img src="http://oo77gy3uq.bkt.clouddn.com/qrcode_for_gh.jpg" alt="公众号二维码"></p>

      
    </div>
    
  </div>
  
    
    <div class="copyright">
        <p><span>本文标题:</span><a href="/2017/04/22/meituan-id/">Leaf——美团点评分布式ID生成系统</a></p>
        <p><span>文章作者:</span><a href="/" title="回到主页">xiaoyou</a></p>
        <p><span>发布时间:</span>2017-04-22, 21:03:00</p>
        <p><span>最后更新:</span>2017-04-26, 14:06:38</p>
        <p>
            <span>原始链接:</span><a class="post-url" href="/2017/04/22/meituan-id/" title="Leaf——美团点评分布式ID生成系统">http://yoursite.com/2017/04/22/meituan-id/</a>
            <span class="copy-path" data-clipboard-text="原文: http://yoursite.com/2017/04/22/meituan-id/　　作者: xiaoyou" title="点击复制文章链接"><i class="fa fa-clipboard"></i></span>
            <script> var clipboard = new Clipboard('.copy-path'); </script>
        </p>
        <p>
            <span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
        </p>
    </div>



    <nav id="article-nav">
        
            <div id="article-nav-newer" class="article-nav-title">
                <a href="/2017/04/10/rocket-in-practice-1/">
                    RocketMQ实战（一）
                </a>
            </div>
        
        
            <div id="article-nav-older" class="article-nav-title">
                <a href="/2017/04/23/distribute-micro-service-1/">
                    微服务业务开发三个难题－拆分、事务、查询（上）
                </a>
            </div>
        
    </nav>

  
</article>

    <div id="toc" class="toc-article">
        <strong class="toc-title">文章目录</strong>
        
            <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#背景"><span class="toc-number">1.</span> <span class="toc-text">背景</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#常见方法介绍"><span class="toc-number">2.</span> <span class="toc-text">常见方法介绍</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#UUID"><span class="toc-number">2.0.1.</span> <span class="toc-text">UUID</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#类snowflake方案"><span class="toc-number">2.0.2.</span> <span class="toc-text">类snowflake方案</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Leaf-segment数据库方案"><span class="toc-number">2.0.3.</span> <span class="toc-text">Leaf-segment数据库方案</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#双buffer优化"><span class="toc-number">2.0.4.</span> <span class="toc-text">双buffer优化</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Leaf高可用容灾"><span class="toc-number">2.0.5.</span> <span class="toc-text">Leaf高可用容灾</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Leaf-snowflake方案"><span class="toc-number">3.</span> <span class="toc-text">Leaf-snowflake方案</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#弱依赖ZooKeeper"><span class="toc-number">3.0.1.</span> <span class="toc-text">弱依赖ZooKeeper</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#解决时钟问题"><span class="toc-number">3.0.2.</span> <span class="toc-text">解决时钟问题</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Leaf现状"><span class="toc-number">4.</span> <span class="toc-text">Leaf现状</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#作者简介"><span class="toc-number">5.</span> <span class="toc-text">作者简介</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#参考资料"><span class="toc-number">6.</span> <span class="toc-text">参考资料</span></a></li></ol>
        
    </div>
    <style>
        .left-col .switch-btn,
        .left-col .switch-area {
            display: none;
        }
        .toc-level-3 i,
        .toc-level-3 ol {
            display: none !important;
        }
    </style>

    <input type="button" id="tocButton" value="隐藏目录"  title="点击按钮隐藏或者显示文章目录">

    <script>
        yiliaConfig.toc = ["隐藏目录", "显示目录", !!"false"];
    </script>



    
<div class="share">
    
        <div class="bdsharebuttonbox">
            <a href="#" class="fa fa-twitter bds_twi" data-cmd="twi" title="分享到推特"></a>
            <a href="#" class="fa fa-weibo bds_tsina" data-cmd="tsina" title="分享到新浪微博"></a>
            <a href="#" class="fa fa-qq bds_sqq" data-cmd="sqq" title="分享给 QQ 好友"></a>
            <a href="#" class="fa fa-files-o bds_copy" data-cmd="copy" title="复制网址"></a>
            <a href="#" class="fa fa fa-envelope-o bds_mail" data-cmd="mail" title="通过邮件分享"></a>
            <a href="#" class="fa fa-weixin bds_weixin" data-cmd="weixin" title="生成文章二维码"></a>
            <a href="#" class="fa fa-share-alt bds_more" data-cmd="more"></i></a>
        </div>
        <script>
            window._bd_share_config={
                "common":{"bdSnsKey":{},"bdText":"Leaf——美团点评分布式ID生成系统　| Lost Youth　","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
        </script>
    

    
</div>







    




    <div class="scroll" id="post-nav-button">
        
            <a href="/2017/04/10/rocket-in-practice-1/" title="上一篇: RocketMQ实战（一）">
                <i class="fa fa-angle-left"></i>
            </a>
        

        <a title="文章列表"><i class="fa fa-bars"></i><i class="fa fa-times"></i></a>

        
            <a href="/2017/04/23/distribute-micro-service-1/" title="下一篇: 微服务业务开发三个难题－拆分、事务、查询（上）">
                <i class="fa fa-angle-right"></i>
            </a>
        
    </div>

    <ul class="post-list"><li class="post-list-item"><a class="post-list-link" href="/2017/05/20/distrute-in-action/">分布式服务化系统一致性的“最佳实干“</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/05/12/spring-boot-in-action/">Spring Boot In Action</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/05/04/mysql-youhua/">我必须得告诉大家的MySQL优化原理</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/26/mysql-bizhibimui/">MySql 必知必会</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/26/java-8-in-action/">Java8 In Action</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/26/java-8-in-practice/">Java8学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/23/distribute-micro-service-1/">微服务业务开发三个难题－拆分、事务、查询（上）</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/23/distribute-micro-service-2/">微服务业务开发三个难题－拆分、事务、查询（下）</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/22/meituan-id/">Leaf——美团点评分布式ID生成系统</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/10/rocket-in-practice-1/">RocketMQ实战（一）</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/10/head-first-git-branch/">Git由浅入深之分支管理</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/10/tomcat-principle/">Tomcat组成与工作原理</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/10/tomcat-cluster/">Tomcat 集群实现源码级别剖析</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/04/mysql-7-join/">Mysql的七种join</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/04/04/hello-world/">Hello World</a></li></ul>




    <script>
        
    </script>
</div>
      <footer id="footer">
    <div class="outer">
        <div id="footer-info">
            <div class="footer-left">
                <i class="fa fa-copyright"></i> 
                2016-2017 xiaoyou
            </div>
            <div class="footer-right">
                <a href="http://hexo.io/" target="_blank" title="快速、简洁且高效的博客框架">Hexo</a>  Theme <a href="https://github.com/MOxFIVE/hexo-theme-yelee" target="_blank" title="简而不减 Hexo 双栏博客主题  v3.5">Yelee</a> by MOxFIVE <i class="fa fa-heart animated infinite pulse"></i>
            </div>
        </div>
        
            <div class="visit">
                
                    <span id="busuanzi_container_site_pv" style='display:none'>
                        <span id="site-visit" title="本站到访数"><i class="fa fa-user" aria-hidden="true"></i><span id="busuanzi_value_site_uv"></span>
                        </span>
                    </span>
                
                
                    <span>| </span>
                
                
                    <span id="busuanzi_container_page_pv" style='display:none'>
                        <span id="page-visit"  title="本页阅读量"><i class="fa fa-eye animated infinite pulse" aria-hidden="true"></i><span id="busuanzi_value_page_pv"></span>
                        </span>
                    </span>
                
            </div>
        
    </div>
</footer>
    </div>
    
<script data-main="/js/main.js" src="//cdn.bootcss.com/require.js/2.2.0/require.min.js"></script>

    <script>
        $(document).ready(function() {
            var iPad = window.navigator.userAgent.indexOf('iPad');
            if (iPad > -1 || $(".left-col").css("display") === "none") {
                var bgColorList = ["#9db3f4", "#414141", "#e5a859", "#f5dfc6", "#c084a0", "#847e72", "#cd8390", "#996731"];
                var bgColor = Math.ceil(Math.random() * (bgColorList.length - 1));
                $("body").css({"background-color": bgColorList[bgColor], "background-size": "cover"});
            }
            else {
                var backgroundnum = 5;
                var backgroundimg = "url(/background/bg-x.jpg)".replace(/x/gi, Math.ceil(Math.random() * backgroundnum));
                $("body").css({"background": backgroundimg, "background-attachment": "fixed", "background-size": "cover"});
            }
        })
    </script>





<div class="scroll" id="scroll">
    <a href="#" title="返回顶部"><i class="fa fa-arrow-up"></i></a>
    <a href="#comments" onclick="load$hide();" title="查看评论"><i class="fa fa-comments-o"></i></a>
    <a href="#footer" title="转到底部"><i class="fa fa-arrow-down"></i></a>
</div>
<script>
    // Open in New Window
    
        var oOpenInNew = {
            
            
            
            
            
            
             archives: ".archive-article-title", 
             miniArchives: "a.post-list-link", 
            
             friends: "#js-friends a", 
             socail: ".social a" 
        }
        for (var x in oOpenInNew) {
            $(oOpenInNew[x]).attr("target", "_blank");
        }
    
</script>

<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js">
</script>
  </div>
</body>
</html>